Miller rabin algorithm
What is the Miller-Rabin Primality Test?
Miller-Rabin is a probabilistic algorithm used to determine whether a given number is prime. It's widely used in cryptographic applications because it's both fast and reliable, though it technically gives a probabilistic result rather than an absolute proof of primality.
Key Components:
1. Number to test (n)
2. Number of rounds (k)
3. Random bases
4. Decomposition n-1 = 2^s * d
5. Witness loop testing
Core Process:
1. Write n-1 as 2^s * d (d odd)
2. Pick random base a
3. Test sequence x = a^d, a^(2d), a^(4d)... mod n
4. Check for specific patterns
5. Repeat k times with different bases
Mathematical Steps:
1. Express n-1 = 2^s * d
2. For each round:
• Choose random a (1 < a < n-1)
• Calculate x = a^d mod n
• If x = 1 or x = n-1, continue
• Square x up to s-1 times
• If no n-1 found, composite
Example:
Testing n = 221:
1. 221-1 = 220 = 2^2 * 55
2. s = 2, d = 55
3. Choose base a = 174:
• x₀ = 174^55 mod 221 = 47
• x₁ = 47^2 mod 221 = 168
• x₂ = 168^2 mod 221 = 1
4. Number is composite